# Definition for singly-linked list.
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

from typing import Optional


class Solution:
    def partition(self, head: Optional[ListNode], x: int) -> Optional[ListNode]:
        l,r = left,right = ListNode(0),ListNode(0)

        while head is not None:
            if head.val < x:
                l.next =head
                head = head.next
                l = l.next
            else:
                r.next = head
                head = head.next
                r = r.next
        l.next = right.next
        r.next = None
        return left.next



if __name__ == '__main__':
    head = [1,4,3,2,5,2]
    x = 3
    soluton = Solution()
    val = soluton.partition(head,x)
    print(val)